Print all permutations of a given string (incl. duplicates)

Print all permutations of a given string (including duplicates).

def permute_string(S):

    if len(S) == 0:
        return ['']

    prev_list = permute_string(S[1:len(S)])
    next_list = []

    for i in range(0, len(prev_list)):
        for j in range(0, len(S)):
            new_str = prev_list[i][0:j] + S[0] + prev_list[i][j:len(S)-1]
            if new_str not in next_list:
                next_list.append(new_str)

    return next_list

# test
print(permute_string('ABCD'))

Output:

['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA',\
 'ACDB', 'CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', \
 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']

See also

https://www.w3resource.com/python-exercises/math/python-math-exercise-16.php